package com.wj.heap;

/**
 * @author wen.jie
 * @date 2021/8/24 9:53
 */
public class Heap<T extends Comparable<T>> {

    private T[] items;

    private int N;

    public Heap(int capacity) {
        this.items = (T[])new Comparable[capacity+1];
        this.N = 0;
    }

    //比较i位置元素是否比j位置元素小
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    //交换i位置元素和j位置元素
    private void exch(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    /**
     * @author wen.jie
     * @date 2021/8/24 10:59
     * 向堆中添加一个元素
     */
    public void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    /**
     * @author wen.jie
     * @date 2021/8/24 9:59
     * 上浮算法
     */
    private void swim(int k) {
        while (k > 1 && less(k/2, k)){
            exch(k/2, k);
            k = k/2;
        }
    }

    /**
     * @author wen.jie
     * @date 2021/8/24 9:59
     * 下沉算法
     */
    private void sink(int k) {
        while (2*k <= N){
            int j = 2*k;
            if(j < N && less(j, j+1)) j++;
            if(!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    /**
     * @author wen.jie
     * @date 2021/8/24 10:59
     * 删除堆中最大的元素
     */
    public T delMax() {
        T t = items[1];
        items[1] = null;
        exch(N--, 1);
        sink(1);
        return t;
    }
}
